sampling-based motion planning

https://scrapbox.io/files/653e830871225b001b35972a.png

collision detectionをブラックボックスとして扱い、geometric modelとプランニングを分離する。問題が解けるかどうか弱い保証しかない。

resolution completeness 解があれば有限の時間で解を見つけるが、解がないときは無限に計算する。

metri space 距離が定義されている空間

Lp距離 $ \rho(x,x') = (\sum_{i=1}^n |x_i -x'_i|^p)^{1/p}

厳密な距離計算が難しいときは、pseudometricsが使われる。

probabilistic completeness もし解が存在するなら、サンプリングの回数を無限に増やせばその解を見つける